00100			     COMPUTER VISION
00200				   by
00300	             Thomas O. Binford, Stanford University    and
00400	             Jay M. Tenenbaum,  Stanford Research Institute
00500	
00600	
00700				Introduction.
00800	
00805	Intelligent computers require knowledge of their environment, and
00810	the most effective means of acquiring such knowledge is by seeing.
00815	Vision will open a new realm of computer applications. Weather 
00820	analysis from cloud maps and medical diagnosis from x-rays and
00825	blood cell counts are two of many high volume data processing tasks that
00830	require pictorial input. Man-machine communication will be facilitated 
00835	if a person can directly show the computer a real object, rather than
00840	having to describe it symbolically. Designers, for example, could
00845	then easily obtain a computerized structural analysis of scale models.
00850	
00855	A particularly exciting application domain is industrial automation.
00860	Today in industry there are hundreds of machines called industrial 
00865	robots. These programmable manipulators can repetitively execute a precise
00870	sequence of motions but have no sensors and are thus unable to react dynamically
00875	to contingencies. Simple sensors and a minicomputer could, at 
00880	slight additional cost, turn these manipulators into true robots.
00900	Primitive visual skills would enable these machines to  align  mating  parts  in  assembly  operations,
00905	increase reliability by self-calibration, detect flaws and avoid disasters.
00910	Vision will also minimize the present need for precise positioning of parts at
00912	each work station; parts could instead be transported in a bin and picked
00915	out as needed.
00920	
00925	The study of perception also provides valuable insights into
00930	human and machine information processing.
01605	Many of the problems encountered are widespread in
01700	intelligence: How is knowledge represented? 
01800	How does it guide in drawing conclusions from perceptual data?
01900	How does existing knowledge interact with conclusions drawn  from  an image 
01905	to acheive learning?
01910	Issues that arise in the implementation of vision systems have broad
01915	relevance to computer science: How shoulc a complex task be
01920	partitioned into modules? How should the modules communicate to
01925	share their knowledge and special capabilities? How should systems with
01930	highly interdependent modules be structured to facilitate modification?
02100	
02105	Techniques developed for machine perception
02200	cannot be taken literally as models for biological systems because of
02300	differences in hardware and gaps in our  knowledge.  However, fundamental
02400	limitations  are  shared,  suggesting that some of the principles might
02450	also be found in nature. The research may, in turn, 
02500	occasionally borrow from biology,  but  we  cannot  copy
02600	nature,  since  again, the  details  are  not  yet known  and  the  hardware  is
02700	different.
05700	
05800	
05805	Historically, computer vision emerged from the study of two dimensional
05810	pattern recognition. However, it is seldom possible to apply the 
05815	mathematical formalisms developed for classification to the 
05820	analysis of real scenes. Consider the visual requirements for an
05825	organism such as a robot. It must
06000	manipulate or avoid objects, not just
06100	classify   them.     Manipulation    requires    three-dimensional
06200	interpretations  and spatial relations of objects. 
06400	In problems like  character recognition, it was attractive
06500	to simply save images or feature vectors, then match against an image
06600	or  part  of  an image.  But in real scenes, objects occlude one another, they have parts
06700	with joints  that  move  separately,  there  are  many  viewpoints,  many
06800	possible  objects,  and  many combinations of objects. Object classes, moreover,
06900	are often defined by function, not shape (eg. the class of coffee  cups).  
07100	Direct  template
07200	matching techniques are impractical for these requirements, except in
07300	very carefully controlled applications. Perception involves
07305	complex deductions to understand an image in terms of a priori knowledge
07310	of the world.
     

00100		ELEMENTS OF A VISUAL SYSTEM
00200	
00300	The  computer  eye is some form of tv camera with color filters and a
00400	turret or zoom  lens  for  closeup  views.    The  computer  controls
00500	filters,  lens  and  other  parameters to optimize the image for each
00600	task [Tenenbaum].  A recent study has suggested alternative sensors 
00700	to overcome the inadequate dynamic range of television systems [Binford].
00705	Range information greatly simplifies the interpretation of scenes.
00800	Humans use depth information  obtained  from  stereo and a variety of inferred
00805	cues such as motion parallax and the size of known objects. Since these techniques
00810	require subtantial processing, it is easier for machines to obtain depth
00815	by direct measurement.
00900	Several  depth  sensors based on triangulation have been built [Agin,
01000	Shirai, Munson]. 
01200	
01300	The  image  is  read  into  memory  as  an array of brightness values
01400	(typically 300x300) with 4-8 bits for each sample for each color. The
01500	process  of  interpreting  this  mass  of  numbers  into  a  symbolic
01600	description can  be  thought  of  as  subdivided  into  segmentation,
01700	representation, and interpretation.
01800	
01900	The  process of segmentation partitions a scene into meaningful
02000	entities which  may  be  recognizable.    Segmentation  in  character
02100	recognition  is simple since printed characters are spatially separated
02200	and have high contrast with white paper. It is harder to segment objects in  a
02300	real  scene  (even  simple  scenes)  since objects may overlap and will not
02305	usually be separable from the local background by a single attribute like brightness contrast.
02310	Instead, segmentation must proceed by seeking regions of uniform
02400	brightness, color, or texture
02500	(itself  a  complex descriptor), or regions with regular boundaries.
02600	Segmentation
02700	may  also  depend  on  inferred depth  cues (e.g., texture gradients or
02705	suspected occlusion).
02900	
03000	In what form can we represent objects internally in the computer?  The
03100	simplest  form is a pictorial template, an array of brightness values
03200	to be matched directly against fragments of  scenes  by  correlation.
03300	Given  the  inadequacies  of  this  representation,  we must describe
03400	partitioned regions symbolically in terms of extracted features  like
03500	color,  size,  texture, and shape.  All these properties are inferred
03600	by complex processes from the image.  Simple descriptors for shape or
03700	texture may be used in simple tasks and limited context.  Shape might
03800	be described by the ratio of the squared perimeter to the area  of  a
03900	region.  More sophisticated shape representations, needed for a wider
04000	range of tasks, are described later.
04100	
04200	Interpretation is often expressed as  computing  a  distance  measure
04300	between  an  object and a stored model.  For simple cases that can be
04400	useful.   When objects are occluded, there must be a  partial  match.
04500	When  objects  are  not  identical, judgments of similarity depend on
04600	representation of shape and representation of the task, in  order  to
04700	define  important  differences.  The most useful approach is to build
04800	up  symbolic  descriptions  and   make   symbolic   descriptions   of
04900	differences.   Sometimes,  there  are few enough models that matching
05000	with each model is possible. More generally, the observed features 
05100	must first be used to retrieve likely models from a large visual memory.
05200	
05205	The integration of segmentation, representation and interpretation to acheive
05210	perception is illustrated by a system built at the University of Edinburgh
05215	[Barrow] which can recognize a small set of ordinary objects such as 
05220	pencils, eye-glasses and teacups. Objects are presented against a contrasting
05225	background. Segmentation is acheived by partitioning the scene into
05230	regions of uniform brightness. Objects are represented by relational
05235	graphs detailing gross attributes (size, shape) of their principle regions 
05240	and spatial constraints between them. Interpretation is accomplished by mapping
05245	the relational graph descriptions of known objects onto the segmented
05250	regions obtained from the scene and seeking the best match.
05255	
05260	Experience with early bottom-up systems of this type led to the realization
05265	that the three basic processes of a perceptual system were highly interdependent;
05400	one cannot proceed sequentially through segmentation, representation  and
05500	interpretation   and   expect   to   obtain   a  globally  consistent
05600	interpretation for all objects  in  a  scene.  One problem is that  no reliable
05602	basis exists for judging the global significance of segmentation boundaries 
05603	using local similarity criteria.
05605	Segmentation  must  be
05700	guided   by   interpretation   to   choose   among  many  alternative
05800	partitionings, that which leads to a globally consistent and reasonable
05805	description of the scene.
     

00100			BLOCKS WORLD
00200	
00300	To avoid some of these difficulties, research concentrated  initially
00400	on  scenes  of  toy blocks.  Roberts' important work opened the field [].
00500	Objects were represented as built up  of  three  primitive  parts,  a
00600	block,  a  wedge, and a hexagonal prism. The program assumed it would
00700	first obtain perfect line drawings. Interpretation  meant  finding  a
00800	three-dimensional model which after translation, rotation and scaling
00900	could be projected to match part of the image.  The recognized  piece
01000	was  then  cut  away  and  the remainder considered.  Primitives were
01100	represented by their vertices in three  dimensions.    To  decide  on
01200	likely  image  points  which  belonged  to a single body, the program
01300	attempted  to  identify  unobscured  polygons,  then  match  sets  of
01400	vertices  to topologically similar model vertices. Line drawings were
01500	formed by a sequence of local operations.  Candidate edge points were
01600	considered  by  thresholding the gradient of intensity. Isolated edge
01700	points were discarded.  Connected line  fragments  were  concatenated
01800	into  lines  which  were  segmented  at corners by a sequential least
01900	squares line fit.  Merging of colinear lines bridged some gaps.
02000	
02100	That system organization has proven inadequate. It is not  enough  to
02200	use  models and template matching. Producing perfect line drawings is
02300	not practical:  some  lines  are  missed;  shadows,  reflections  and
02400	surface  markings  cause  extra  lines;  errors made at one stage are
02500	compounded by later stages.  These deficiencies motivated  subsequent
02600	research.
02700	
02800	Guzman  []  found  it possible to segment complex scenes into objects
02900	without template matching, by observing that some vertices give local
03000	evidence  that adjacent regions belong to the same body. In figure 1,
03100	vertices A,B,C,E,G and H give evidence that adjacent regions belong to the
03200	same  body, while vertex F does not. 
03205	Vertex  D which resembles G gives misleading  evidence.  To avoid such
03300	coincidences, the program required confirmation.      Regions  linked
03400	twice  were  joined  into clusters; regions linked twice to a cluster
03500	were also joined.  Regions linked only to a single cluster were  also
03600	joined  to  that  cluster. Eventually, the program evolved to include
03700	inhibitions against certain links by requiring similar conditions  at
03800	both  ends  of  a  line.   Other  links  were introduced without much
03900	motivation.   
03950	
03975	This program was an important advance.    Bodies  could
04000	be  segmented  without  recognition and without explicit models.  The
04100	program did surprisingly well, but had problems with holes and  other
04200	non-convexities,  and  with  accidental  alignment.
04300	being told the background.
04310	Guzman also could not cope well with imperfect line drawings. His program
04315	would fail of figure 2 because a missing line makes region R3 common
04320	to both the block and wedge. Falk [  ] was able to avoid some of the errors
04325	associated with missing boundaries by using a Guzman like approach to link
04330	line segments likely to belong to the same object instead of regions.
04332	
04335	The limited generality of both these programs was due to the fact that they were implemented
04340	as a collection of adhoc heuristics for segmentation with no explicit
04345	understanding of line drawings. Thus, while Falk himself realized
04350	that regions like R3 could not arise in a scene containing only
04355	trihedral solids, his program could not reason at this level.
05000	Huffman  []  and  Clowes [] made theoretical analyses of objects with
05100	only  trihedral  vertices  (three  planes  at  each  vertex).      By
05200	classifying  edges  as  convex,  concave  and  obscuring,  they could
05300	require consistent labels for a drawing, and reject some drawings  as
05400	impossible  objects  under their conditions.   Waltz [] expanded that
05500	labelling of lines to include cracks  and  whether  adjacent  regions
05600	were  shadowed  or illuminated. Each vertex had many interpretations.
05700	It would seem that such large  numbers  of  possible  interpretations
05800	would   be   unmanageable.    instead,  the  increased  precision  of
05900	descriptions allows rapid discarding of wrong  interpretations.   Not
06000	only  are solutions possible, they are quickly obtained. Instead of a
06100	complete tree  search,  it  was  adequate  to  consider  vertices  in
06200	sequence, eliminating inconsistent interpretations as each new vertex
06300	was added.  This produced all possible interpretations  of  a  scene.
06400	However,   some   evaluations  were  possible  to  choose  reasonable
06500	interpretations, in cases with ambiguous interpretations.
06505	A detailed survey of the work through Huffman appears in a recent text by
06510	Duda and Hart [1973].
06600	
06700	
06800	
06900	
07000	
07100	The best performance in extracting line drawings from television images of polyhedra is given by the  Shirai
07200	[]  and  the  Binford-Horn [] line finders.  Shirai's system performs
07300	better, but requires large  contrast  between objects and  background
07400	(e.g., white  on black), and finds only features and objects for which cues
07500	are available from context.   The Binford-Horn system is able to find
07600	most  lines  in  a  scene  of  white  blocks on a white background in
07700	arbitrary lighting.  It misses a few lines which can usually be inferred from those that were found, and
07800	garbles  some  vertices.    The  two  are complementary and should be
07900	combined.
08000	
08100	The two programs are based on different principles.  Shirai's program
08200	began  with  only  outer  boundaries,  and  tried to guess as much as
08300	possible at each stage.    At vertices,  the  extension  of  boundary
08400	lines  was  tested.  Completions for unterminated lines were searched
08500	for.    Additional lines were tested for at vertices, including  some
08600	parallel  to lines at adjacent vertices.  The use of context involved
08700	not changing thresholds, but using special-purpose operators:  verify
08800	a line at known position and angle; find a line through a vertex. The
08900	Binford-Horn system was intended to provide the  base  for  a  system
09000	such  as Shirai's by providing a partial line drawing without special
09100	background.  It used a local directional edge operator and an optimal
09200	curve  sequential  decision process to extend curves and test at each
09300	extension, whether to keep, terminate, or extend further.
09350	Figure 3 illustrates the complexity of scenes handled by Shirai's program.
09400	
09500	It is interesting  to  compare  these  systems  with  the  biological
09600	system.   Directional  edge  operators  are  scanned  over  the image
09700	[Binford, Hueckel]; these compare with the edge detector cells discovered by Heubel and Wiesel[]  in
09800	higher  animals.    In  practice,  large gradients at reflections and
09900	curved surfaces cause masses of spurious edge fragments.  These  were
10000	eliminated  by  subtracting  the  local  average  at each point, thus
10100	subtracting out smooth gradients [Binford].  This process is familiar
10200	as lateral inhibition in the retina of animals.
10300	
10400	
10500	
     

00100			REAL WORLD VISION
00200	
00300	
00400	
00500	The  blocks  world  illustrates  many  basic   aspects   of   machine
00600	perception,   but   many   other  critical  problems  encountered  in
00700	perceiving real world scenes do not  arise.   Important  problems  in
00800	segmentation   were   avoided  by  using  uniformly  painted  blocks.
00900	Segmentation  of  boundaries  was  specialized  to  straight   lines.
01000	The region-growing and edge-finding techniques developed in this context
01100	cannot cope with the textures and variations of brightness that
01105	predominate in the real world.
01200	
01205	The elaborate topological descriptions that characterized simple
01210	polyhedra are inappropriate or unobtainable for most real world objects.
01300	In some cases we must rely only on gross characteristics
01400	of shape, texture and other features, e.g., to distinguish trees from mountains. In
01500	other cases, we require  more  complex  descriptions  than
01600	characterized  polyhedra,  as  in  descriptions  of machined parts or
01700	people.
01800	
01900	It is not conceivable in  real  world  scenes  to  search  through  a
02000	complete set of known prototypes seeking interpretations.  The system
02100	must limit interpretations to those familiar in the context, and  use
02200	brief  descriptions  to  select  a  small  subset  of possible object
02300	interpretations.  Segmentation can then attempt to find
02305	uniform regions for attributes which best 
02310	characterize these objects.
02400	
02405	The key problem faced in real world vision is information overload,
02410	and it must be faced, as above, by tightly coordinating segmentation and interpretation
02415	with world knowledge.
02600	The overload is
02700	not to be solved by  merely  building  faster  computers  and  bigger
02800	memories;  hardware  improvements will aid adequate techniques but do
02900	little for exhaustive techniques.
03000	
03100	Description of simple polyhedral scenes was  difficult  enough;  with
03200	these  added  obstacles,  is there hope for success in perceiving the
03300	real world? 
03305	We think so!  Although it may not be possible (or even meaningful)
03310	to obtain exhaustive descriptions of real scenes, such descriptions are seldom needed;
03315	a system will usually be concerned with only a few objects objects 
03320	required to complete a specific task. 
03400	For blocks, we restricted our programs to
03500	black and white images and distinguished structures of blocks  solely
03600	on  the  basis  of  shape.  In the real world, there is a tremendous 
03605	redundancy of visual cues. We can use color, texture,
03700	depth, size (which is not very  relevant  for  blocks),  and  surface
03800	orientation, as well as shape.  Finally, real world objects are usually found in 
03805	well defined contexts; e.g., telephones are expected on tables but not in 
03810	waste baskets.
03815	Recognition of a few promminent landmarks, combined with a priori knowledge
03820	of the environment can thus severely restrict what objects may be
03825	present in each part of the scene. While these objects may be difficult
03830	to describe, there will usually be sufficient cues available to 
03835	discriminate easily amongst the alternatives. Real world vision can be
03840	viewed as a strategy problem: Given a task, decide where to look for
03845	objects of interest and then how to distinguish them from others that
03850	might also be present.
     

00200	
00205	The principle work to date on real world vision has concentrated
00210	on segmentation and representation.
00300	Studies for agricultural and earth resources surveys have  considered
00400	texture as a two-dimensional problem.  Bajcsy [] has analyzed outdoor
00500	scenes for which perspective and  three-dimensional  description  are
00600	important.      Textures  were  described  hierarchically in terms of simpler texture
00700	elements and their spatial relationships.  Descriptors  for  texture  elements
00800	and   relations   were   derived  from  Fourier  analysis.  Typical
00900	attributes were directionality (if any),  size,  contrast,  and  spacing  of  texture
01000	elements.    The  Fourier  transform  was  found troublesome,however, and
01100	color descriptors were added to improve performance.  Some depth relations  could
01200	be  observed  from  texture gradient.   An attempt was made to obtain
01300	consistent interpretations by first confirming region  boundaries  by
01400	independent properties, making three-dimensional interpretations, and
01500	matching region descriptors with those of sky, trees, grass, etc.  in
01600	a world model.
01700	
01800	The  quality  of  interpretation  was  limited  by  unreliability  of
01900	region-growing processes. Further work in outdoor scenes attempts  to
02000	incorporate  the  world  model  and  interpretation  into  the region
02100	growing process. Regions are merged not only because of similarity of
02200	properties, but because the consistency of semantic interpretation is
02300	improved.
     

00200	
00300	
00305	Typical robot tasks such as manipulation, collision avoidance, display
00310	and recognition were analyzed to determine
00600	computational primitives required for descriptions of shape.
00800	Although some would disagree,
00900	the general criteria for shape representation are [ ]:
00905	
01000	a) Representations should be symbolic at a high level in order
01100	to interface with knowledge of the problem domain.
01200	b) Representations should depend on segmentation into parts,
01300	which may have subparts. Primitives should allow a natural choice
01305	of parts.
01400	c) Primitives should be three-dimensional volume descriptions,
01500	rather than surface descriptions.
01600	d) Descriptions should be generative.  A modest collection of
01700	primitives should allow description of a vast set of objects.
01800	
01805	We will outline one representation that fulfils these desiderata for a large
01807	class of curved objects.
01810	Objects are described in terms  of components
01820	which are simple to  describe, and the relationships of  these parts.
01835	A useful shape primitive for many curved objects 
01840	is an arbitrary  space curve,
01850	and normal  cross-sections along  this axis (figure 5).  
01851	Snake-like objects, helices, toroids, and locally helical and toroidal shapes
01852	are naturally described [Binford 71].
01854	Our basic  criteria for
01860	accepting a  piece as simple  are that the  direction of the  axis be
01870	continuous  and that  the cross-section  function along  the  axis be
01880	continuous.  We look  for portions with  large changes in  the cross-
01890	section,  and  consider  them as  likely  places  for  segmenting the
01900	object.  The  segmentation  process  must  be  flexible  and  able to
01910	generate  alternate  propositions.  A  higher  level   routine  will 
01920	ultimately select from the alternatives.  Figure 6 shows an experimentally
01921	obtained computer description of a doll [Agin 72].
     

00100			INDUSTRIAL APPLICATIONS
00150	
00300	Recently, several laboratories have begun to apply techniques
00400	from perception research to practical industrial tasks.
00500	General Motors laboratories has succeeded in mounting a wheel on 
00600	an axle. Stanford Research Institute and Hitachi Ltd. have each
00700	demonstrated systems which can distinguish sheet metal parts
00800	on a moving conveyor belt and determine their orientation to enable
00900	manipulation. Template matching techniques were used to take 
01000	advantage of the two dimensional nature of these tasks. Moreover,
01100	the conveyor demonstrations relied on the contrast between shiny metalic parts 
01200	and the black belt to simplify segmentation. Many industrial processes 
01300	share similar constraints or can be readily redesigned to do so.
01400	We thus expect a proliferation of industrial applications of 
01500	computer perception in the near future.